#include <iostream>
using namespace std;

const int kMaxA = 1010;
const int kInf = 1e9;

int f[2][kMaxA * 2];

void Renew(int& a, int b) {
  a = min(a, b);
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int T;
  for (cin >> T; T; T--) {
    int n;
    fill(f[0], f[0] + kMaxA * 2, kInf);
    cin >> n;
    f[0][0] = 0;
    for (int i = 1; i <= n; i++) {
      int a;

      cin >> a;

      fill(f[i & 1], f[i & 1] + kMaxA * 2, kInf);
      for (int j = 0; j < kMaxA * 2; j++) {
        int new_j;

        new_j = j + a;
        if (new_j < kMaxA * 2) {
          Renew(f[i & 1][new_j], max(f[(i - 1) & 1][j], new_j));
        }
        new_j = j - a;
        if (new_j < 0) {
          Renew(f[i & 1][0], f[(i - 1) & 1][j] - new_j);
        } else {
          Renew(f[i & 1][new_j], f[(i - 1) & 1][j]);
        }
      }
    }
    int ans = kInf;
    for (int j = 0; j < kMaxA * 2; j++) {
      Renew(ans, f[n & 1][j]);
    }
    cout << ans << "\n";
  }
  return 0;
}